/** 
 * @file scheduler.c
   @brief Functions that provide the scheduler interface.
 */
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include "scheduler.h"
#include "random.h"

/** Gets the calling thread's schedule from the hash table of schedules. */
static schedule *get_schedule();

/** Sorts a linked list of events.
    Written by Simon Tatham
    http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
*/
static event * listsort(event *);

/** Hash table for storing schedules for each resource thread. Each thread accesses their scheduling by using its thread id. */
schedule_list *schedule_table[HASHSIZE];

void add_to_schedule(schedule *s, event *e)
{
  if(e == NULL)
    {
      return;
    }
  event *tmp = s->head;
  s->head = e;
  e->next = tmp;
  s->head = listsort(s->head); /* sort list */
}

event * next_event()
{
  schedule *s = get_schedule();
  event *next = s->head;
  s->head = next->next;
  return next;
}

int has_event()
{
  schedule *s = get_schedule();
  return (s->head != NULL) ? 1 : 0;
}

schedule *sort_schedule(schedule *s) {
  s->head = listsort(s->head);
  return s;
}

/** Compares two events' timestamps and returns 1 if a > b -1 if a < b and 0 a == b. Used by listsort. */
int cmp(event *a, event *b) {
  if (a->timestamp->tv_sec == b->timestamp->tv_sec)
    {
      return (a->timestamp->tv_nsec > b->timestamp->tv_nsec) ? 1 : (a->timestamp->tv_nsec < b->timestamp->tv_nsec) ? -1 : 0;
    }
  return (a->timestamp->tv_sec > b->timestamp->tv_sec) ? 1 : (a->timestamp->tv_nsec < b->timestamp->tv_nsec) ? -1 : 0;
 }

event *listsort(event *list) {
  event *p, *q, *e, *tail;
  int insize, nmerges, psize, qsize, i;
  
  /*
   * Silly special case: if `list' was passed in as NULL, return
   * NULL immediately.
   */
  if (!list) {
    return NULL;
  }
  
  insize = 1;

  while (1) {
    p = list;
    list = NULL;
    tail = NULL;
      
    nmerges = 0;  /* count number of merges we do in this pass */
      
    while (p) {
      nmerges++;  /* there exists a merge to be done */
      /* step 'insize' places along from p */
      q = p;
      psize = 0;
      for (i = 0; i < insize; i++) {
        psize++;
        q = q->next;
        if (!q) break;
      }
            
      /* if q hasn't fallen off end, we have two lists to merge */
      qsize = insize;
            
      /* now we have two lists; merge them */
      while (psize > 0 || (qsize > 0 && q)) {
              
        /* decide whether next element of merge comes from p or q */
        if (psize == 0) {
          /* p is empty; e must come from q. */
          e = q; q = q->next; qsize--;
        } else if (qsize == 0 || !q) {
          /* q is empty; e must come from p. */
          e = p; p = p->next; psize--;
        } else if (cmp(p,q) <= 0) {
          /* First element of p is lower (or same);
           * e must come from p. */
          e = p; p = p->next; psize--;
        } else {
          /* First element of q is lower; e must come from q. */
          e = q; q = q->next; qsize--;
        }
        
        /* add the next element to the merged list */
        if (tail) {
          tail->next = e;
        } else {
          list = e;
        }
        tail = e;
      }
            
      /* now p has stepped 'insize' places along, and q has too */
      p = q;
    }
	
    tail->next = NULL;
        
    /* If we have done only one merge, we're finished. */
    if (nmerges <= 1)   /* allow for nmerges==0, the empty list case */
      return list;
        
    /* Otherwise repeat, merging lists twice the size */
    insize *= 2;
  }
}

void schedule_event(event *e)
{
  add_to_schedule(get_schedule(), e);
}

schedule *get_schedule() {
  hashed target = int_hash((unsigned long int) pthread_self());
  schedule_list *list;
  for(list = schedule_table[target]; list != NULL; list = list->next)
    {
      if(list->key == (unsigned long int) pthread_self())
        {
          return list->s;
        }
    }
  return NULL;
}

void setup_schedule() {
  if(get_schedule() != NULL)
    {
      return;
    }
  hashed target = int_hash((unsigned long int) pthread_self());
  schedule_list *list = malloc(sizeof(schedule_list));
  list->key = (unsigned long int) pthread_self();
  list->s = malloc(sizeof(schedule));
  list->s->head = NULL;
  list->next = schedule_table[target];
  schedule_table[target] = list;
}
